#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define data char
typedef struct TreeE
{
	data val;
	struct TreeE* left;
	struct TreeE* right;
}*pTE,TE;
void add(pTE* p)
{
	data a;
	scanf("%c", &a);
	if (a == '#')
	{
		*p = NULL;
	}
	else
	{
		(*p) = (TE*)malloc(sizeof(struct TreeE));
		if (*p == NULL)
			return;
		(*p)->val = a;
		add(&(*p)->left);
		add(&(*p)->right);
		return;
	}
}
void print(TE* p)
{
	if (p == NULL)
		return;
	printf("%c ", p->val);
	print(p->left);
	print(p->right);
}
void FREE(TE* p)
{
	if (p == NULL)
		return;
	free(p);
	FREE(p->left);
	FREE(p->right);
}
int main()
{
	TE* ps = NULL;
	add(&ps);
	print(ps);
	FREE(ps);
	return 0;
}